<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-26.html">previous</a></span><span>, <a href="book-Z-H-28.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_sec_4.2"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_4.2">4.2&nbsp;&nbsp;Variations on a Scheme -- Lazy Evaluation</a></h2><p>


<a name="%_idx_4666"></a><a name="%_idx_4668"></a>
<a name="%_idx_4670"></a><a name="%_idx_4672"></a>Now that we have an evaluator expressed as a Lisp program, we can
experiment with alternative choices in language design simply by
modifying the evaluator.  Indeed, new languages are often invented by
first writing an evaluator that embeds the new language within an
existing high-level language.  For example, if we wish to discuss some
aspect of a proposed modification to Lisp with another member of the
Lisp community, we can supply an evaluator that embodies
the change.  The recipient can then experiment with the new
evaluator and send back comments as further modifications.  Not only
does the high-level implementation base make it easier to test and
debug the evaluator; in addition, the embedding enables the designer
to snarf<a name="call_footnote_Temp_575" href="#footnote_Temp_575"><sup><small>31</small></sup></a> features
from the underlying language, just as our embedded Lisp evaluator
uses primitives and control structure from the underlying Lisp.  Only
later (if ever) need the designer go to the trouble of building a
complete implementation in a low-level language or in hardware.  In
this section and the next we explore some variations on Scheme that
provide significant additional expressive power.<p>

<a name="%_sec_4.2.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.1">4.2.1&nbsp;&nbsp;Normal Order and Applicative Order</a></h3><p>

<p>

<a name="%_idx_4680"></a><a name="%_idx_4682"></a>In section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1">1.1</a>, where we began our discussion
of models of evaluation, we noted that Scheme is an <em>applicative-order</em> language, namely, that all the arguments to Scheme
procedures are evaluated when the procedure is applied.  In
contrast, <em>normal-order</em> languages delay evaluation of procedure arguments
until the actual argument values are needed.
Delaying evaluation of procedure arguments until the
last possible moment (e.g., until they are required by a primitive
operation) is called <a name="%_idx_4684"></a><em>lazy evaluation</em>.<a name="call_footnote_Temp_576" href="#footnote_Temp_576"><sup><small>32</small></sup></a>
Consider the procedure<p>

<p><p><tt>(define&nbsp;(try&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;a&nbsp;0)&nbsp;1&nbsp;b))<br>
</tt><p><p>
Evaluating <tt>(try 0 (/ 1 0))</tt> generates an error in Scheme.  With
lazy evaluation, there would be no error.  Evaluating the expression
would return 1, because the argument <tt>(/ 1 0)</tt> would
never be evaluated.<p>

An example that exploits lazy evaluation is the 
definition of a procedure <tt>unless</tt><p>

<p><p><tt>(define&nbsp;(unless&nbsp;condition&nbsp;usual-value&nbsp;exceptional-value)<br>
&nbsp;&nbsp;(if&nbsp;condition&nbsp;exceptional-value&nbsp;usual-value))<br>
</tt><p><p>
that can be used in expressions such as<p>

<p><p><tt>(unless&nbsp;(=&nbsp;b&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(display&nbsp;&quot;exception:&nbsp;returning&nbsp;0&quot;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0))<br>
</tt><p><p>
This won't work in an applicative-order language because both the
usual value and the exceptional value will be evaluated before
<tt>unless</tt> is called (compare exercise&nbsp;<a href="book-Z-H-10.html#%_thm_1.6">1.6</a>).  An
advantage of lazy evaluation is that some procedures, such as <tt>unless</tt>, can do useful computation even if evaluation of some of their
arguments would produce errors or would not terminate.<p>

If the body of a procedure is entered before an argument has been
evaluated we say that the procedure is <a name="%_idx_4686"></a><em>non-strict</em> in that
argument.  If the argument is evaluated before the body of the
procedure is entered we say that the procedure is <a name="%_idx_4688"></a><em>strict</em> in that
argument.<a name="call_footnote_Temp_577" href="#footnote_Temp_577"><sup><small>33</small></sup></a>
In a purely applicative-order language, all procedures are strict in
each argument.  In a purely normal-order language, all compound
procedures are non-strict in each argument, and primitive procedures may be
either strict or non-strict.  There are also languages (see
exercise&nbsp;<a href="#%_thm_4.31">4.31</a>) that give programmers
detailed control over the strictness of the procedures they define.<p>

A striking example of a procedure that can usefully be made non-strict
is <tt>cons</tt> (or, in general, almost any constructor for data
structures).  One can do useful computation, combining elements to
form data structures and operating on the resulting data structures,
even if the values of the elements are not known.  It makes perfect
sense, for instance, to compute the length of a list without knowing
the values of the individual elements in the list.  We will exploit
this idea in section&nbsp;<a href="#%_sec_4.2.3">4.2.3</a> to implement the
streams of chapter&nbsp;3 as lists formed of non-strict <tt>cons</tt>
pairs.<p>

<p><a name="%_thm_4.25"></a>
<b>Exercise 4.25.</b>&nbsp;&nbsp;Suppose that (in ordinary applicative-order Scheme) we define <tt>unless</tt>
as shown above and then define <tt>factorial</tt> in terms of <tt>unless</tt> as<p>

<p><p><tt>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(unless&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;n&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1))<br>
</tt><p><p>
What happens if we attempt to evaluate <tt>(factorial 5)</tt>?  Will our
definitions work in a normal-order language?
<p><p>

<p><a name="%_thm_4.26"></a>
<b>Exercise 4.26.</b>&nbsp;&nbsp;<a name="%_idx_4692"></a><a name="%_idx_4694"></a>Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of
lazy evaluation for implementing things such as <tt>unless</tt>.  Ben
points out that it's possible to implement <tt>unless</tt> in applicative
order as a special form.
Alyssa counters that, if one did that, <tt>unless</tt> would be merely
syntax, not a procedure that could be used in conjunction with
higher-order procedures.  Fill in the details on both sides of the
argument.  Show how to implement <tt>unless</tt> as a derived expression
(like <tt>cond</tt> or <tt>let</tt>),
and give an example of a situation where it might be useful to have
<tt>unless</tt> available as a procedure, rather than as a special form.

<p><p>

<a name="%_sec_4.2.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.2">4.2.2&nbsp;&nbsp;An Interpreter with Lazy Evaluation</a></h3><p>

In this section we will implement a normal-order language that is
the same as Scheme except that compound procedures are non-strict
in each argument.  Primitive procedures will still be strict.
It is not difficult to modify the evaluator of
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> so that the language it interprets behaves
this way.  Almost all the required changes center around procedure
application.<p>

The basic idea is that, when applying a procedure, the interpreter
must determine which arguments are to be
evaluated and which are to be
delayed.  The delayed arguments are not
evaluated; instead, they are transformed into objects called <a name="%_idx_4696"></a><em>thunk</em>s.<a name="call_footnote_Temp_580" href="#footnote_Temp_580"><sup><small>34</small></sup></a>
The thunk must contain the information required to produce the value
of the argument when it is needed, as if it had been evaluated at
the time of the application.  Thus, the thunk must contain the
argument expression and the environment in
which the procedure application is being evaluated.<p>

<a name="%_idx_4704"></a><a name="%_idx_4706"></a>The process of evaluating the expression in a thunk is called <em>forcing</em>.<a name="call_footnote_Temp_581" href="#footnote_Temp_581"><sup><small>35</small></sup></a>
In general, a thunk will be forced only when its value is needed:
when it is passed to a primitive procedure that
will use the value of the thunk; when it is the
value of a predicate of a conditional; and when it
is the value of an operator that is about to be applied as a procedure.
One design choice we have available is whether or not to <a name="%_idx_4710"></a><em>memoize</em> thunks, as we did with delayed objects in
section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>.  With memoization, the first time a
thunk is forced, it stores the value that is computed.  Subsequent
forcings simply return the stored value without repeating the
computation.  We'll make our interpreter memoize, because this is
more efficient for many applications.  There are tricky
considerations here, however.<a name="call_footnote_Temp_582" href="#footnote_Temp_582"><sup><small>36</small></sup></a><p>

<a name="%_sec_Temp_583"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_583">Modifying the evaluator</a></h4><p>

The main difference between the lazy evaluator and the one in
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a> is in the handling of procedure
applications in <tt>eval</tt> and <tt>apply</tt>.<p>

<a name="%_idx_4720"></a>The <tt>application?</tt> clause of <tt>eval</tt> becomes<p>

<p><p><tt>((application?&nbsp;exp)<br>
&nbsp;(apply&nbsp;(actual-value&nbsp;(operator&nbsp;exp)&nbsp;env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(operands&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;env))<br>
</tt><p><p>
This is almost the same as the <tt>application?</tt> clause of <tt>eval</tt>
in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>.  For lazy evaluation, however,
we call <tt>apply</tt> with the operand expressions, rather than the
arguments produced by evaluating them.  Since we will need the environment to
construct thunks if the arguments are to be delayed, we must pass this as well.
We still evaluate the
operator, because <tt>apply</tt> needs the actual procedure to be applied
in order to dispatch on its type (primitive versus compound) and apply it.<p>

Whenever we need the actual value of an expression, we use
<p><p><tt><a name="%_idx_4722"></a>(define&nbsp;(actual-value&nbsp;exp&nbsp;env)<br>
&nbsp;&nbsp;(force-it&nbsp;(eval&nbsp;exp&nbsp;env)))<br>
</tt><p><p>
instead of just <tt>eval</tt>, so that if the expression's value
is a thunk, it will be forced.<p>

Our new version of <tt>apply</tt> is also almost the same as the
version in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>.  The difference is
that <tt>eval</tt> has passed in unevaluated operand expressions:
For primitive procedures (which are strict), we evaluate all the
arguments before applying the primitive;
for compound procedures (which are non-strict) we delay all the
arguments before applying the procedure.<p>

<p><p><tt><a name="%_idx_4724"></a>(define&nbsp;(apply&nbsp;procedure&nbsp;arguments&nbsp;env)<br>
&nbsp;&nbsp;(cond&nbsp;((primitive-procedure?&nbsp;procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(apply-primitive-procedure<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;procedure<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-of-arg-values&nbsp;arguments&nbsp;env)))&nbsp;&nbsp;<em>;&nbsp;changed</em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((compound-procedure?&nbsp;procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(eval-sequence<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(procedure-body&nbsp;procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(extend-environment<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(procedure-parameters&nbsp;procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-of-delayed-args&nbsp;arguments&nbsp;env)&nbsp;<em>;&nbsp;changed</em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(procedure-environment&nbsp;procedure))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&quot;Unknown&nbsp;procedure&nbsp;type&nbsp;--&nbsp;APPLY&quot;&nbsp;procedure))))<br>
</tt><p><p>
The procedures that process the arguments are just like <tt>list-of-values</tt> from section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, except that
<tt>list-of-delayed-args</tt> delays the arguments instead of evaluating
them, and <tt>list-of-arg-values</tt> uses <tt>actual-value</tt> instead
of <tt>eval</tt>:<p>

<p><p><tt><a name="%_idx_4726"></a>(define&nbsp;(list-of-arg-values&nbsp;exps&nbsp;env)<br>
&nbsp;&nbsp;(if&nbsp;(no-operands?&nbsp;exps)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(actual-value&nbsp;(first-operand&nbsp;exps)&nbsp;env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-of-arg-values&nbsp;(rest-operands&nbsp;exps)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;env))))<br>
<a name="%_idx_4728"></a>(define&nbsp;(list-of-delayed-args&nbsp;exps&nbsp;env)<br>
&nbsp;&nbsp;(if&nbsp;(no-operands?&nbsp;exps)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(delay-it&nbsp;(first-operand&nbsp;exps)&nbsp;env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-of-delayed-args&nbsp;(rest-operands&nbsp;exps)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;env))))<br>
</tt><p><p><p>

The other place we must change the evaluator is in the handling of
<tt>if</tt>, where we must use <tt>actual-value</tt> instead
of <tt>eval</tt> to get the value of the predicate expression
before testing whether it is true or false:<p>

<p><p><tt><a name="%_idx_4730"></a>(define&nbsp;(eval-if&nbsp;exp&nbsp;env)<br>
&nbsp;&nbsp;(if&nbsp;(true?&nbsp;(actual-value&nbsp;(if-predicate&nbsp;exp)&nbsp;env))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(eval&nbsp;(if-consequent&nbsp;exp)&nbsp;env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(eval&nbsp;(if-alternative&nbsp;exp)&nbsp;env)))<br>
</tt><p><p><p>

<a name="%_idx_4732"></a>Finally, we must change the <tt>driver-loop</tt>
procedure (section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>) to use <tt>actual-value</tt> instead
of <tt>eval</tt>, so that if a delayed value
is propagated back to the read-eval-print loop, it will be forced
before being printed.  We also change the prompts to indicate that
this is the lazy evaluator:<p>

<p><p><tt><a name="%_idx_4734"></a>(define&nbsp;input-prompt&nbsp;&quot;;;;&nbsp;L-Eval&nbsp;input:&quot;)<br>
(define&nbsp;output-prompt&nbsp;&quot;;;;&nbsp;L-Eval&nbsp;value:&quot;)<br>
<a name="%_idx_4736"></a>(define&nbsp;(driver-loop)<br>
&nbsp;&nbsp;(prompt-for-input&nbsp;input-prompt)<br>
&nbsp;&nbsp;(let&nbsp;((input&nbsp;(read)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((output<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(actual-value&nbsp;input&nbsp;the-global-environment)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(announce-output&nbsp;output-prompt)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(user-print&nbsp;output)))<br>
&nbsp;&nbsp;(driver-loop))<br>
</tt><p><p><p>

With these changes made, we can start the evaluator and test it.  The
successful evaluation of the <tt>try</tt> expression discussed in
section&nbsp;<a href="#%_sec_4.2.1">4.2.1</a> indicates that the interpreter is
performing lazy evaluation:<p>

<p><p><tt>(define&nbsp;the-global-environment&nbsp;(setup-environment))<br>
(driver-loop)<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(define&nbsp;(try&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;a&nbsp;0)&nbsp;1&nbsp;b))<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
<i>ok</i><br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(try&nbsp;0&nbsp;(/&nbsp;1&nbsp;0))<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
<i>1</i><br>
</tt><p><p><p>


<a name="%_sec_Temp_584"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_584">Representing thunks</a></h4><p>

<a name="%_idx_4738"></a>
Our evaluator must arrange to create thunks when procedures are
applied to arguments and to force these thunks later.  A thunk must
package an expression together with the environment, so that the
argument can be produced later.
To force the thunk, we simply extract the expression and environment
from the thunk and evaluate the expression in the environment.
We use <tt>actual-value</tt> rather than <tt>eval</tt> so that in case the
value of the expression is itself a thunk, we will force that, and so
on, until we reach something that is not a thunk:<p>

<p><p><tt><a name="%_idx_4740"></a>(define&nbsp;(force-it&nbsp;obj)<br>
&nbsp;&nbsp;(if&nbsp;(thunk?&nbsp;obj)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(actual-value&nbsp;(thunk-exp&nbsp;obj)&nbsp;(thunk-env&nbsp;obj))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;obj))<br>
</tt><p><p><p>

One easy way to package an expression with an environment is to make a
list containing the expression and the environment.
Thus, we create a thunk as follows:<p>

<p><p><tt><a name="%_idx_4742"></a>(define&nbsp;(delay-it&nbsp;exp&nbsp;env)<br>
&nbsp;&nbsp;(list&nbsp;'thunk&nbsp;exp&nbsp;env))<br>
<br>
(define&nbsp;(thunk?&nbsp;obj)<br>
&nbsp;&nbsp;(tagged-list?&nbsp;obj&nbsp;'thunk))<br>
<br>
(define&nbsp;(thunk-exp&nbsp;thunk)&nbsp;(cadr&nbsp;thunk))<br>
<br>
(define&nbsp;(thunk-env&nbsp;thunk)&nbsp;(caddr&nbsp;thunk))<br>
</tt><p><p><p>

Actually, what we want for our interpreter is not quite this, but
rather thunks that have been memoized.
When a thunk is forced, we will turn it into an evaluated thunk
by replacing the stored expression with its value and
changing the <tt>thunk</tt> tag so that it can be recognized as
already evaluated.<a name="call_footnote_Temp_585" href="#footnote_Temp_585"><sup><small>37</small></sup></a><p>

<p><p><tt>(define&nbsp;(evaluated-thunk?&nbsp;obj)<br>
&nbsp;&nbsp;(tagged-list?&nbsp;obj&nbsp;'evaluated-thunk))<br>
<br>
(define&nbsp;(thunk-value&nbsp;evaluated-thunk)&nbsp;(cadr&nbsp;evaluated-thunk))<br>
<a name="%_idx_4748"></a>(define&nbsp;(force-it&nbsp;obj)<br>
&nbsp;&nbsp;(cond&nbsp;((thunk?&nbsp;obj)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((result&nbsp;(actual-value<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(thunk-exp&nbsp;obj)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(thunk-env&nbsp;obj))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(set-car!&nbsp;obj&nbsp;'evaluated-thunk)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(set-car!&nbsp;(cdr&nbsp;obj)&nbsp;result)&nbsp;&nbsp;<em>;&nbsp;replace&nbsp;<tt>exp</tt>&nbsp;with&nbsp;its&nbsp;value</em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(set-cdr!&nbsp;(cdr&nbsp;obj)&nbsp;'())&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;forget&nbsp;unneeded&nbsp;<tt>env</tt></em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((evaluated-thunk?&nbsp;obj)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(thunk-value&nbsp;obj))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;obj)))<br>
</tt><p><p>
Notice that the same <tt>delay-it</tt> procedure works both with and
without memoization.<p>

<p><a name="%_thm_4.27"></a>
<b>Exercise 4.27.</b>&nbsp;&nbsp;Suppose we type in the following definitions to the lazy evaluator:
<p><p><tt>(define&nbsp;count&nbsp;0)<br>
(define&nbsp;(id&nbsp;x)<br>
&nbsp;&nbsp;(set!&nbsp;count&nbsp;(+&nbsp;count&nbsp;1))<br>
&nbsp;&nbsp;x)<br>
</tt><p><p>
Give the missing values in the following sequence of
interactions, and explain your answers.<a name="call_footnote_Temp_587" href="#footnote_Temp_587"><sup><small>38</small></sup></a>
<p><p><tt>(define&nbsp;w&nbsp;(id&nbsp;(id&nbsp;10)))<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
count<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
&lt;<em>response</em>&gt;<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
w<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
&lt;<em>response</em>&gt;<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
count<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
&lt;<em>response</em>&gt;<br>
</tt><p><p>
<p><p>

<p><a name="%_thm_4.28"></a>
<b>Exercise 4.28.</b>&nbsp;&nbsp;<tt>Eval</tt> uses <tt>actual-value</tt> rather than <tt>eval</tt>
to evaluate the operator before passing it to <tt>apply</tt>,
in order to force the value of the operator.
Give an example that demonstrates the need for this forcing.
<p><p>

<p><a name="%_thm_4.29"></a>
<b>Exercise 4.29.</b>&nbsp;&nbsp;Exhibit a program that you would expect to run much more slowly
without memoization than with memoization.  Also, consider the
following interaction, where the <tt>id</tt> procedure is defined as in
exercise&nbsp;<a href="#%_thm_4.27">4.27</a> and <tt>count</tt> starts at 0:
<p><p><tt>(define&nbsp;(square&nbsp;x)<br>
&nbsp;&nbsp;(*&nbsp;x&nbsp;x))<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(square&nbsp;(id&nbsp;10))<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
&lt;<em>response</em>&gt;<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
count<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
&lt;<em>response</em>&gt;<br>
</tt><p><p>
Give the responses both when the evaluator memoizes and when it does not.

<p><p>

<p><a name="%_thm_4.30"></a>
<b>Exercise 4.30.</b>&nbsp;&nbsp;Cy D. Fect, a reformed C programmer, is worried that some side effects
may never take place, because the lazy evaluator doesn't force the
expressions in a sequence.
Since the value of an expression in a sequence other than the last one
is not used (the expression is there only for its effect, such as
assigning to a variable or printing), there can be no subsequent use
of this value (e.g., as an argument to a primitive procedure) that
will cause it to be forced.  Cy thus thinks that when evaluating
sequences, we must force all expressions in the sequence except the
final one.  He proposes to modify <tt>eval-sequence</tt> from
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> to use <tt>actual-value</tt> rather
than <tt>eval</tt>:<p>

<p><p><tt>(define&nbsp;(eval-sequence&nbsp;exps&nbsp;env)<br>
&nbsp;&nbsp;(cond&nbsp;((last-exp?&nbsp;exps)&nbsp;(eval&nbsp;(first-exp&nbsp;exps)&nbsp;env))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(actual-value&nbsp;(first-exp&nbsp;exps)&nbsp;env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(eval-sequence&nbsp;(rest-exps&nbsp;exps)&nbsp;env))))<br>
</tt><p><p><p>

<p><p>a. Ben Bitdiddle thinks Cy is wrong.
He shows Cy the <tt>for-each</tt> procedure described in
exercise&nbsp;<a href="book-Z-H-15.html#%_thm_2.23">2.23</a>, which gives an important example of
a sequence with side effects:<p>

<p><p><tt><a name="%_idx_4750"></a>(define&nbsp;(for-each&nbsp;proc&nbsp;items)<br>
&nbsp;&nbsp;(if&nbsp;(null?&nbsp;items)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'done<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(proc&nbsp;(car&nbsp;items))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(for-each&nbsp;proc&nbsp;(cdr&nbsp;items)))))<br>
</tt><p><p>
He claims that the evaluator in the text (with the original <tt>eval-sequence</tt>) handles this correctly:<p>

<p><p><tt><i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(for-each&nbsp;(lambda&nbsp;(x)&nbsp;(newline)&nbsp;(display&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;57&nbsp;321&nbsp;88))<br>
<i>57</i><br>
<i>321</i><br>
<i>88</i><br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
<i>done</i><br>
</tt><p><p>
Explain why Ben is right about the behavior of <tt>for-each</tt>.<p>

<p><p>b. Cy agrees that Ben is right about the <tt>for-each</tt> example,
but says that that's not the kind of program he was thinking about
when he proposed his change to <tt>eval-sequence</tt>.
He defines the following two procedures in the lazy evaluator:<p>

<p><p><tt>(define&nbsp;(p1&nbsp;x)<br>
&nbsp;&nbsp;(set!&nbsp;x&nbsp;(cons&nbsp;x&nbsp;'(2)))<br>
&nbsp;&nbsp;x)<br>
<br>
(define&nbsp;(p2&nbsp;x)<br>
&nbsp;&nbsp;(define&nbsp;(p&nbsp;e)<br>
&nbsp;&nbsp;&nbsp;&nbsp;e<br>
&nbsp;&nbsp;&nbsp;&nbsp;x)<br>
&nbsp;&nbsp;(p&nbsp;(set!&nbsp;x&nbsp;(cons&nbsp;x&nbsp;'(2)))))<br>
</tt><p><p>
What are the values of <tt>(p1 1)</tt> and <tt>(p2 1)</tt> with the
original <tt>eval-sequence</tt>?
What would the values be with Cy's proposed change to <tt>eval-sequence</tt>?<p>

<p><p>c. Cy also points out that changing <tt>eval-sequence</tt> as he proposes
does not affect the behavior of the example in part a.
Explain why this is true.<p>

<p><p>d. How do you think sequences ought to be treated in the lazy evaluator?
Do you like Cy's approach, the approach in the text, or some other approach?

<p><p>

<p><a name="%_thm_4.31"></a>
<b>Exercise 4.31.</b>&nbsp;&nbsp;<a name="%_idx_4752"></a>The approach taken in this section is somewhat unpleasant, because it
makes an incompatible change to Scheme.  It might be nicer to
implement lazy evaluation as an <em>upward-compatible extension</em>,
that is, so that ordinary Scheme programs will work as before.  We can
do this by extending the syntax of procedure declarations to let the user
control whether or not arguments are to be delayed.  While we're at
it, we may as well also give the user the choice between delaying with
and without memoization.  For example, the definition
<p><p><tt>(define&nbsp;(f&nbsp;a&nbsp;(b&nbsp;lazy)&nbsp;c&nbsp;(d&nbsp;lazy-memo))<br>
&nbsp;&nbsp;<tt>...</tt>)<br>
</tt><p><p>
would define <tt>f</tt> to be a procedure of four arguments, where the
first and third arguments are evaluated when the procedure is called,
the second argument is delayed, and the fourth argument is both
delayed and memoized.  Thus, ordinary procedure definitions will
produce the same behavior as ordinary Scheme, while adding the <tt>lazy-memo</tt> declaration to each parameter of every compound procedure
will produce the behavior of the lazy evaluator defined in this
section. Design and implement the changes required to produce such an
extension to Scheme.  You will have to implement new syntax procedures
to handle the new syntax for <tt>define</tt>.  You must also arrange for
<tt>eval</tt> or <tt>apply</tt> to determine when arguments are to be delayed, and to
force or delay arguments accordingly, and you must arrange for forcing
to memoize or not, as appropriate.

<p><p>

<a name="%_sec_4.2.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.3">4.2.3&nbsp;&nbsp;Streams as Lazy Lists</a></h3><p>


<a name="%_idx_4754"></a><a name="%_idx_4756"></a><a name="%_idx_4758"></a><a name="%_idx_4760"></a><a name="%_idx_4762"></a>
<a name="%_idx_4764"></a><a name="%_idx_4766"></a><a name="%_idx_4768"></a><a name="%_idx_4770"></a>In section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>, we showed how to implement streams
as delayed lists.  We introduced special forms <tt>delay</tt> and <tt>cons-stream</tt>, which allowed us to construct a ``promise'' to compute
the <tt>cdr</tt> of a stream, without actually fulfilling that promise
until later.  We could use this general technique of introducing
special forms whenever we need more control over the evaluation process,
but this is awkward.  For one thing, a special form is not a
first-class object like a procedure, so we cannot use it together with
higher-order procedures.<a name="call_footnote_Temp_592" href="#footnote_Temp_592"><sup><small>39</small></sup></a>  Additionally,
we were forced to create streams as a new kind of data object
similar but not identical to lists, and this required us to
reimplement many ordinary list operations (<tt>map</tt>, <tt>append</tt>, and
so on) for use with streams.<p>


With lazy evaluation, streams and lists can be identical, so there is
no need for special forms or for separate list and stream operations.
All we need to do is to arrange matters so that <tt>cons</tt> is
non-strict.  One way to accomplish this is to extend the lazy
evaluator to allow for non-strict primitives, and to implement <tt>cons</tt> as one of these.  An easier way is to recall
(section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a>) that there is no fundamental need to
implement <tt>cons</tt> as a primitive at all.  Instead, we can represent
<a name="%_idx_4772"></a>pairs as procedures:<a name="call_footnote_Temp_593" href="#footnote_Temp_593"><sup><small>40</small></sup></a><p>

<p><p><tt><a name="%_idx_4774"></a>(define&nbsp;(cons&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(lambda&nbsp;(m)&nbsp;(m&nbsp;x&nbsp;y)))<br>
<a name="%_idx_4776"></a>(define&nbsp;(car&nbsp;z)<br>
&nbsp;&nbsp;(z&nbsp;(lambda&nbsp;(p&nbsp;q)&nbsp;p)))<br>
<a name="%_idx_4778"></a>(define&nbsp;(cdr&nbsp;z)<br>
&nbsp;&nbsp;(z&nbsp;(lambda&nbsp;(p&nbsp;q)&nbsp;q)))<br>
</tt><p><p><p>

In terms of these basic operations, the standard definitions of the
list operations will work with infinite lists (streams) as well as
finite ones, and the stream operations can be implemented as list operations.
Here are some examples:<p>

<p><p><tt><a name="%_idx_4780"></a>(define&nbsp;(list-ref&nbsp;items&nbsp;n)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(car&nbsp;items)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-ref&nbsp;(cdr&nbsp;items)&nbsp;(-&nbsp;n&nbsp;1))))<br>
<a name="%_idx_4782"></a>(define&nbsp;(map&nbsp;proc&nbsp;items)<br>
&nbsp;&nbsp;(if&nbsp;(null?&nbsp;items)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(proc&nbsp;(car&nbsp;items))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(map&nbsp;proc&nbsp;(cdr&nbsp;items)))))<br>
<a name="%_idx_4784"></a>(define&nbsp;(scale-list&nbsp;items&nbsp;factor)<br>
&nbsp;&nbsp;(map&nbsp;(lambda&nbsp;(x)&nbsp;(*&nbsp;x&nbsp;factor))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items))<br>
<a name="%_idx_4786"></a>(define&nbsp;(add-lists&nbsp;list1&nbsp;list2)<br>
&nbsp;&nbsp;(cond&nbsp;((null?&nbsp;list1)&nbsp;list2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((null?&nbsp;list2)&nbsp;list1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(cons&nbsp;(+&nbsp;(car&nbsp;list1)&nbsp;(car&nbsp;list2))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add-lists&nbsp;(cdr&nbsp;list1)&nbsp;(cdr&nbsp;list2))))))<br>
<a name="%_idx_4788"></a>(define&nbsp;ones&nbsp;(cons&nbsp;1&nbsp;ones))<br>
<a name="%_idx_4790"></a>(define&nbsp;integers&nbsp;(cons&nbsp;1&nbsp;(add-lists&nbsp;ones&nbsp;integers)))<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(list-ref&nbsp;integers&nbsp;17)<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
<i>18</i><br>
</tt><p><p><p>


Note that these lazy lists are even lazier than the streams of
chapter&nbsp;3:  The <tt>car</tt> of the list, as well as the <tt>cdr</tt>, is
delayed.<a name="call_footnote_Temp_594" href="#footnote_Temp_594"><sup><small>41</small></sup></a>
In fact, even accessing the <tt>car</tt> or <tt>cdr</tt> of a lazy
pair need not force the value of a list element.  The value will be
forced only when it is really needed -- e.g., for use as the
argument of a primitive, or to be printed as an answer.<p>

Lazy pairs also help with the problem that arose with streams in
section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>, where we found that
formulating stream models of systems with loops may require us to
sprinkle our programs with <a name="%_idx_4798"></a><a name="%_idx_4800"></a>explicit <tt>delay</tt> operations, beyond the
ones supplied by <tt>cons-stream</tt>.  With lazy evaluation, all
arguments to procedures are delayed uniformly.  For instance, we can
implement procedures to integrate lists and solve differential
equations as we originally intended in
section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>:<p>

<p><p><tt><a name="%_idx_4802"></a>(define&nbsp;(integral&nbsp;integrand&nbsp;initial-value&nbsp;dt)<br>
&nbsp;&nbsp;(define&nbsp;int<br>
&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;initial-value<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add-lists&nbsp;(scale-list&nbsp;integrand&nbsp;dt)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int)))<br>
&nbsp;&nbsp;int)<br>
<a name="%_idx_4804"></a>(define&nbsp;(solve&nbsp;f&nbsp;y0&nbsp;dt)<br>
&nbsp;&nbsp;(define&nbsp;y&nbsp;(integral&nbsp;dy&nbsp;y0&nbsp;dt))<br>
&nbsp;&nbsp;(define&nbsp;dy&nbsp;(map&nbsp;f&nbsp;y))<br>
&nbsp;&nbsp;y)<br>
<i>;;;&nbsp;L-Eval&nbsp;input:</i><br>
(list-ref&nbsp;(solve&nbsp;(lambda&nbsp;(x)&nbsp;x)&nbsp;1&nbsp;0.001)&nbsp;1000)<br>
<i>;;;&nbsp;L-Eval&nbsp;value:</i><br>
<i>2.716924</i></tt><p><p><p>

<p><a name="%_thm_4.32"></a>
<b>Exercise 4.32.</b>&nbsp;&nbsp;Give some examples that illustrate the difference between the streams
of chapter&nbsp;3 and the ``lazier'' lazy lists described in this section.
How can you take advantage of this extra laziness?
<p><p>

<p><a name="%_thm_4.33"></a>
<b>Exercise 4.33.</b>&nbsp;&nbsp;Ben Bitdiddle tests the lazy list implementation given above by
evaluating the expression
<p><p><tt>(car&nbsp;'(a&nbsp;b&nbsp;c))<br>
</tt><p><p>
To his surprise, this produces an error.  After some thought, he
realizes that the ``lists'' obtained by reading in quoted expressions
are different from the lists manipulated by the new definitions of
<tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>.  Modify the evaluator's
treatment of quoted expressions so that quoted lists typed at the
driver loop will produce true lazy lists.

<p><p>

<p><a name="%_thm_4.34"></a>
<b>Exercise 4.34.</b>&nbsp;&nbsp;Modify the driver loop for the evaluator so that lazy pairs and lists
will print in some reasonable way.  (What are you going to do about
infinite lists?)  You may also need to modify the representation of
lazy pairs so that the evaluator can identify them in order
to print them.

<p><p>

<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_575" href="#call_footnote_Temp_575"><sup><small>31</small></sup></a> Snarf: ``To grab, especially a large document or
<a name="%_idx_4674"></a><a name="%_idx_4676"></a><a name="%_idx_4678"></a>file for the purpose of using it either with or without the owner's
permission.''  Snarf down: ``To snarf, sometimes with the connotation
of absorbing, processing, or understanding.''  (These definitions were
snarfed from Steele et al. 1983.  See also Raymond 1993.)

<p><a name="footnote_Temp_576" href="#call_footnote_Temp_576"><sup><small>32</small></sup></a> The difference between the ``lazy'' terminology and
the ``normal-order'' terminology is somewhat fuzzy.  Generally, ``lazy''
refers to the mechanisms of particular evaluators, while ``normal-order''
refers to the semantics of languages, independent of any particular
evaluation strategy.  But this is not a hard-and-fast distinction, and
the two terminologies are often used interchangeably.

<p><a name="footnote_Temp_577" href="#call_footnote_Temp_577"><sup><small>33</small></sup></a> The ``strict'' versus ``non-strict'' terminology means essentially the
same thing as ``applicative-order'' versus ``normal-order,'' except that
it refers to individual procedures and arguments rather than to the
language as a whole.  At a conference on programming languages you
might hear someone say, ``The normal-order language <a name="%_idx_4690"></a>Hassle has certain
strict primitives.  Other procedures take their arguments by lazy
evaluation.''

<p><a name="footnote_Temp_580" href="#call_footnote_Temp_580"><sup><small>34</small></sup></a> The word <em>thunk</em> was invented by an informal
<a name="%_idx_4698"></a><a name="%_idx_4700"></a><a name="%_idx_4702"></a>working group that was discussing the implementation of call-by-name
in Algol 60.  They observed that most of the analysis of (``thinking
about'') the expression could be done at compile time; thus, at run
time, the expression would already have been ``thunk'' about (Ingerman
et al. 1960).

<p><a name="footnote_Temp_581" href="#call_footnote_Temp_581"><sup><small>35</small></sup></a> This is analogous to the use of <tt>force</tt>
<a name="%_idx_4708"></a>on the delayed objects that were introduced in chapter&nbsp;3 to represent
streams.  The critical difference between what we are
doing here and what we did in chapter&nbsp;3 is that we are building
delaying and forcing into the evaluator, and thus making this uniform
and automatic throughout the language.

<p><a name="footnote_Temp_582" href="#call_footnote_Temp_582"><sup><small>36</small></sup></a> Lazy evaluation combined with memoization is sometimes
<a name="%_idx_4712"></a>referred to as <em>call-by-need</em> argument passing, in contrast to
<em>call-by-name</em> argument passing.  <a name="%_idx_4714"></a><a name="%_idx_4716"></a>(Call-by-name, introduced in
Algol 60, is similar to non-memoized lazy evaluation.)
As language designers, we can build our evaluator to memoize,
not to memoize, or leave this an option for programmers
(exercise&nbsp;<a href="#%_thm_4.31">4.31</a>).  As you might expect
from chapter&nbsp;3, these choices raise issues that become both subtle and
confusing in the presence of assignments.  (See
exercises&nbsp;<a href="#%_thm_4.27">4.27</a> and&nbsp;<a href="#%_thm_4.29">4.29</a>.)
<a name="%_idx_4718"></a>An excellent article by Clinger (1982) attempts to clarify the
multiple dimensions of confusion that arise here.

<p><a name="footnote_Temp_585" href="#call_footnote_Temp_585"><sup><small>37</small></sup></a> Notice that we also erase the <tt>env</tt> from the thunk once the
expression's value has been computed.  This makes no difference in the
values returned by the interpreter.  It does help save space,
however, because removing the reference from the thunk to the <tt>env</tt>
once it is no longer needed allows this structure to be
<a name="%_idx_4744"></a><a name="%_idx_4746"></a><em>garbage-collected</em> and its
space recycled, as we will discuss in section&nbsp;<a href="book-Z-H-33.html#%_sec_5.3">5.3</a>.<p>

Similarly, we could have allowed unneeded environments in the memoized
delayed objects of section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a> to be garbage-collected,
by having <tt>memo-proc</tt> do something like <tt>(set! proc '())</tt>
to discard the procedure <tt>proc</tt> (which includes the environment
in which the <tt>delay</tt> was evaluated) after storing its value.

<p><a name="footnote_Temp_587" href="#call_footnote_Temp_587"><sup><small>38</small></sup></a> This exercise
demonstrates that the interaction between lazy evaluation and side
effects can be very confusing.  This is just what you might expect
from the discussion in chapter&nbsp;3.

<p><a name="footnote_Temp_592" href="#call_footnote_Temp_592"><sup><small>39</small></sup></a> This is precisely the issue with the <tt>unless</tt> procedure,
as in exercise&nbsp;<a href="#%_thm_4.26">4.26</a>.

<p><a name="footnote_Temp_593" href="#call_footnote_Temp_593"><sup><small>40</small></sup></a> This is the procedural representation described in
exercise&nbsp;<a href="book-Z-H-14.html#%_thm_2.4">2.4</a>.  Essentially any procedural representation
(e.g., a message-passing implementation) would do as well.  Notice
that we can install these definitions in the lazy evaluator simply by
typing them at the driver loop.  If we had originally included <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> as primitives in the global
environment, they will be redefined.  (Also see
exercises&nbsp;<a href="#%_thm_4.33">4.33</a> and&nbsp;<a href="#%_thm_4.34">4.34</a>.)

<p><a name="footnote_Temp_594" href="#call_footnote_Temp_594"><sup><small>41</small></sup></a> This permits us to create delayed versions of more general kinds of
<a name="%_idx_4792"></a>list structures, not just sequences.  Hughes 1990 discusses some
<a name="%_idx_4794"></a><a name="%_idx_4796"></a>applications of ``lazy trees.''

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-26.html">previous</a></span><span>, <a href="book-Z-H-28.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
